import scala.collection.mutable.ListBuffer

/**
 * K means算法
 * 进行虚拟机聚类划分
 *
 * @author lanyangji
 * @date 2019/12/10 15:11
 */
object K_Means_Advanced extends App {

  /**
   * 模拟虚拟机节点坐标
   */
  val nodeList = List[Node](
    Node(0.0, 0.0),
    Node(1.0, 2.0),
    Node(3.0, 1.0),
    Node(8.0, 8.0),
    Node(9.0, 10.0),
    Node(10.0, 7.0)
  )

  /**
   * 分类个数
   */
  val k = 2

  // 定义一个List，用以存储质心
  val centroidList = ListBuffer[Node]()

  /**
   * 递归终结条件
   *
   * 如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值
   * （表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），
   * 我们可以认为聚类已经达到期望的结果，算法终止。
   */
  val terminatedVal = 2

  /**
   * 根据 K-Means 划分聚类
   *
   * @param nlist       原始数据集
   * @param clusterList 聚类划分结果
   * @param clusterSize 聚类个数，即k
   * @return 分类结果
   */
  @scala.annotation.tailrec
  def KMeansDivide(nlist: List[Node], clusterList: ListBuffer[Node], clusterSize: Int): List[Node] = {

    // 如果聚类划分结果数组为空
    if (clusterList.isEmpty) {
      // 定义k个空的list，用以存储聚类划分
      for (i <- 0 until clusterSize) {
        // 先取前前 clusterArr.length 个节点作为质心
        // 作为质心加入到质心集合中
        clusterList += Node(nlist(i).x, nlist(i).y, isCentroid = true, classNo = i)
      }

      // 记录下日志
      println("现在的聚类结果为：\n" + nodeList.mkString("\n") + "\n"
        + "先取前k个节点分别作为质心，加入到质心集合中，现在的质心集合为\n" + clusterList.mkString("\n") + "\n")
    }

    // 计算其他节点到执行的距离
    // centroid 质心
    for (node <- nlist) {

      for (i <- clusterList.indices) {
        val centroid: Node = clusterList(i)
        // println(centroid, i)
        // println(centroid.x, centroid.y)
        // 如果是质心，则计算节点到质心欧式距离
        val distance: Double = math.sqrt(math.pow(node.x - centroid.x, 2) + math.pow(node.y - centroid.y, 2))

        // 如果是第一次计算，直接赋值
        if (i == 0) {
          node.dist = distance
          node.classNo = centroid.classNo
        }

        // 如果不是第一次计算
        // 并且，计算出来的欧式距离小于节点原先的距离，则进行修改
        if (node.dist > distance) {
          // 修改距离
          node.dist = distance
          // 修改分区号
          node.classNo = centroid.classNo
        }
      }
    }

    // 重新计算质心
    val tempGroup: Map[Int, List[Node]] = nodeList.groupBy(_.classNo)
    // 清空原先质心集合之前先克隆一下，方便比较递归结束条件
    val centroidList_clone = centroidList.clone()
    // 清空原先质心集合
    centroidList.clear()
    // 重新计算并添加质心
    for ((k, v) <- tempGroup) {

      val point_x = v.map(_.x).sum / v.size
      val point_y = v.map(_.y).sum / v.size

      // 添加新的质心
      clusterList += Node(point_x, point_y, isCentroid = true, classNo = k)
    }

    // 打印结果
    println("计算各节点与质心之间的距离并分类，现在的聚类结果: \n" + nodeList.mkString("\n"))
    println("现在的质心结果为: \n" + clusterList.mkString("\n"))
    println

    // 递归结束条件
    var isTerminating = true
    for (i <- centroidList.indices) {
      // 计算质心与质心之间的距离
      val centroidDist: Double = math.sqrt(
        math.pow(centroidList(i).x - centroidList_clone(i).x, 2) + math.pow(centroidList(i).y - centroidList_clone(i).y, 2)
      )

      // 如果比限定值大，则不收敛
      if (centroidDist > terminatedVal)
        isTerminating = false
    }
    // 聚类结束
    if (isTerminating) {
      System.err.println("聚类收敛，分类结束")
      return nlist
    }

    // 递归
    KMeansDivide(nlist, clusterList, k)
  }

  // 执行聚类划分方法
  KMeansDivide(nodeList, centroidList, k)
}

/**
 * 节点类
 *
 * x: 节点横坐标
 * y: 节点纵坐标
 * isCentroid:  是否是质心
 * dist:  距离质心的距离
 * classNo: 类号
 */
case class Node(var x: Double, var y: Double, var isCentroid: Boolean = false, var dist: Double = -1.0, var classNo: Int = -1) {

  // 重写下toString：（很坐标，纵坐标，类号）
  override def toString: String = s"($x,\t $y,\t $isCentroid,\t $dist,\t $classNo)"
}

